package 数据结构专栏.简单级别;


/**
 * @DESC 给定一个二叉树，找出其最大深度。
 * <p>
 * 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
 * <p>
 * 说明: 叶子节点是指没有子节点的节点。
 * <p>
 * 示例：
 * 给定二叉树 [3,9,20,null,null,15,7]，
 * <p>
 * 3
 * / \
 * 9  20
 * /  \
 * 15   7
 * 返回它的最大深度 3 。
 * <p>
 * 考过
 * @Date 2020-03-27 15:07
 **/
public class _104_二叉树的最大深度 {
    public static void main(String[] args) {

        TreeNode t1 = new TreeNode(3);
        TreeNode t2 = new TreeNode(9);
        TreeNode t3 = new TreeNode(20);
        t1.left = t2;
        t1.right = t3;
        TreeNode t4 = new TreeNode(15);
        TreeNode t5 = new TreeNode(7);
        t3.left = t4;
        t3.right = t5;

        System.out.println(treeMaxDepth(t1));
        System.out.println(minDepth(t1));


    }


    public static int treeMaxDepth(TreeNode curr) {
        if (curr != null) {
            int left = treeMaxDepth(curr.left);
            int right = treeMaxDepth(curr.right);
            return left > right ? left + 1 : right + 1;
        }

        return 0;
    }


    /**
     * 求二叉树最小深度（递归解法）
     *
     * @param root
     * @return
     */
    public static int minDepth(TreeNode root) {
        TreeNode curr = root;
        if (curr == null) return 0;
        if (curr.left == null && curr.right == null) return 1;

        int min_depth = Integer.MAX_VALUE;
        if (curr.left != null) {
            min_depth = Math.min(minDepth(curr.left), min_depth);
        }
        if (curr.right != null) {
            min_depth = Math.min(minDepth(curr.right), min_depth);
        }
        return min_depth + 1;

    }


    /**
     * 递归三部曲：
     * 找整个递归的终止条件：递归应该在什么时候结束？
     * 找返回值：应该给上一级返回什么信息？
     * 本级递归应该做什么：在这一级递归中，应该完成什么任务？
     *
     * @param root
     * @return
     */
    public static int maxDepth(TreeNode root) {
        //1 . 终止条件 树为空结束递归，并返回当前深度0
        if (root == null) return 0;
        //2. root 左右子树的最大深度
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        //3. 返回左右子数的最大深度+1
        return Math.max(left, right) + 1;
    }

}

